package ljl.alg.wangzheng_camp.round1.dp;

import java.util.Arrays;

public class _300_longest_increase_subseq {
    
    /**
     * 对于每个下标存的是以它结尾的串的递增序列的长度
     * 由于是以它结尾，然后前面的已经算出来了，所以遍历前面的，更新它
     * */
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 1; i < nums.length ; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j])
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }
    
    /**
     * 贪婪 + 二分，不好想，需要糕手
     *
     * 我怀疑我根本就没看懂
     *
     * */
    public int lengthOfLIS2(int[] nums) {
        int[] dp = new int[nums.length + 1];
        dp[1] = nums[0];
        int len = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > dp[len])
                dp[++len] = nums[i];
            else {
                int l = 1, r = len, pos = 0;
                while (l <= r) {
                    int mid = (l + r) >>> 1;
                    if (dp[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                dp[pos + 1] = nums[i];
            }
            
        }
        return len;
    }
}
